﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 최소비용 흐름 문제
    /// </summary>
    class MinimumCost
    {
        int V; //정점수

        List<Edge>[] G; //인접리스트
        int[] h; //포텐셜
        int[] dist; //최단거리
        int[] prevv; //직전의 정점
        int[] preve; //직전의 변

        MinimumCost(int maxV)
        {
            V = maxV;
            G = new List<Edge>[maxV];
            h = new int[maxV];
            dist = new int[maxV];
            prevv = new int[maxV];
            preve = new int[maxV];
        }

        void AddEdge(int from, int to, int cap, int cost)
        {
            G[from].Add(new Edge(from, to, cost, cap, G[to].Count));
            G[to].Add(new Edge(to, from, -cost, 0, G[from].Count - 1));            
        }

        int MinCost(int s, int t, int f)
        {
            int res = 0;
            while (f > 0)
            {
                PriorityQueue<Pair> que = new PriorityQueue<Pair>();
                for (int i = 0; i < V; i++)
                {
                    dist[i] = int.MaxValue;
                }
                dist[s] = 0;
                que.Push(new Pair(0, s));
                while (!que.Empty)
                {
                    Pair p = que.Pop();
                    int v = p.Second;
                    if (dist[v] < p.First) continue;
                    for (int i = 0; i < G[v].Count; i++)
                    {
                        Edge e = G[v][i];
                        dist[e.To] = dist[v] + e.Cost + h[v] - h[e.To];
                        prevv[e.To] = v;
                        preve[e.To] = i;
                        que.Push(new Pair(dist[e.To], e.To));
                    }
                }
            }
            if (dist[t] == int.MaxValue)
            {
                return -1;
            }
            for (int v = 0; v < V; v++)
            {
                h[v] += dist[v];
            }
            int d = f;
            for (int v = t; v != s; v = prevv[v])
            {

            }
            return res;

        }
    }
}
